/**
 * @file
 * Double link list implementation derived from the one
 * used in the linux kernel
 */

#ifndef __LIST_H
#define __LIST_H

#ifndef __UTIL_H
# error "Please include util.h before list.h"
#endif /* __UTIL_H */

struct list_head {
    struct list_head *next, *prev;
};

#define LIST_HEAD_INIT(name)                    \
  { &(name), &(name) }

#define LIST_HEAD(name)                         \
  struct list_head name = LIST_HEAD_INIT(name)

#define INIT_LIST_HEAD(ptr)                     \
  ((ptr)->next = (ptr)->prev = (ptr))

/**
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
inline void __list_add(struct list_head *entry,
                       struct list_head *prev,
                       struct list_head *next);

/**
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
inline void __list_del(struct list_head *prev, 
                       struct list_head *next);

/**
 * list_add_front - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
#define list_add_front(entry, head)             \
  __list_add(entry, head, (head)->next)

/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
#define list_add_back(entry, head)              \
  __list_add(entry, (head)->prev, head)

/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 *
 * Note: list_empty on entry does not return true after this, the entry is in an undefined state.
 */
#define list_del(entry)                                                 \
  (__list_del((entry)->prev, (entry)->next), (entry)->next = (entry)->prev = NULL)

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
#define list_empty(head)                        \
  ((head)->next == (head))

/**
 * list_entry - get the struct for this entry
 * @ptr:the &struct list_head pointer.
 * @type:the type of the struct this is embedded in.
 * @member:the name of the list_struct within the struct.
 */
#define list_entry(ptr, type, member)           \
  get_super_struct(ptr, type, member)

/**
 * list_entry_next - get the struct for the next entry
 * @ptr:the &struct list_head pointer.
 * @type:the type of the struct this is embedded in.
 * @member:the name of the list_struct within the struct.
 */
#define list_entry_next(ptr, type, member)      \
  get_super_struct((ptr)->next, type, member)

/**
 * list_entry_prev - get the struct for the previous entry
 * @ptr:the &struct list_head pointer.
 * @type:the type of the struct this is embedded in.
 * @member:the name of the list_struct within the struct.
 */
#define list_entry_prev(ptr, type, member)      \
  get_super_struct((ptr)->prev, type, member)

/**
 * list_for_each - iterate over a list
 * @pos:the &struct list_head to use as a loop counter.
 * @head:the head for your list.
 */
#define list_for_each(pos, head)                                \
  for (pos = (head)->next; (pos) != (head); pos = (pos)->next)

/**
 * list_for_each_prev-iterate over a list backwards
 * @pos:the &struct list_head to use as a loop counter.
 * @head:the head for your list.
 */
#define list_for_each_prev(pos, head)                           \
  for (pos = (head)->prev; (pos) != (head); pos = (pos)->prev)

/**
 * list_for_each_safe-iterate over a list safe against removal of list entry
 * @pos:the &struct list_head to use as a loop counter.
 * @n:another &struct list_head to use as temporary storage
 * @head:the head for your list.
 */
#define list_for_each_safe(pos, n, head)                                \
  for (pos = (head)->next, n = (pos)->next; (pos) != (head); pos = n, n = (pos)->next)

/**
 * list_for_each_entry-iterate over list of given type
 * @pos:the type * to use as a loop counter.
 * @head:the head for your list.
 * @member:the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)                          \
  for (pos = list_entry((head)->next, typeof(*pos), member); &(pos)->member != (head); pos = list_entry((pos)->member.next, typeof(*pos), member))

/**
 * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry
 * @pos:the type * to use as a loop counter.
 * @n:another type * to use as temporary storage
 * @head:the head for your list.
 * @member:the name of the list_struct within the struct.
 */
#define list_for_each_entry_safe(pos, n, head, member)                  \
  for (pos = list_entry((head)->next, typeof(*pos), member),            \
         n = list_entry((pos)->member.next, typeof(*pos), member);      \
       &(pos)->member != (head);                                        \
       pos = n,                                                         \
         n = list_entry((n)->member.next, typeof(*n), member))

#endif /* __LIST_H */
